﻿// 0829train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
给定一个数组X和正整数K，请找出使表达式：
X[i] - X[i+1] - ... - X[i+K-1]
结果最接近于数组中位数的下标 i ，如果有多个 i 满足条件，请返回最大的 i。
其中，数组中位数：长度为N的数组，按照元素的值大小升序排列后，下标为N/2元素的值

输入
[50,50,2,3],2
输出
1

说明
1. 中位数为50: [50,50,2,3]升序排序后变成[2,3,50,50]，中位数为下标4/2=2的元素50;
2. 计算结果为1: X[50,50,2,3]根据题目计算X[i] - … - X[i+K-1]得出三个数
0 (X[0]-X[1]= 50-50)
48 (X[1]-X[2] = 50-2) //
-1 (X[2]-X[3]= 2-3)
其中48最接近50，因此返回下标1
 */

class Solution01
{
public:
    
    int solve(vector<int>& nums, int K) {
        vector<int>pre_sum;
        int v_size = nums.size();
        pre_sum.resize(v_size + 1);
        for (int i = 0; i < v_size; i++)
        {
            pre_sum[i + 1] = pre_sum[i] + nums[i];
        }

        vector<int>sort_vec = nums;
        sort(sort_vec.begin(), sort_vec.end());

        int middle = sort_vec[v_size / 2];
        int middle_diff = INT_MAX;
        //middle //middle_diff
        //int curr=nums[i]-(pre_sum[i+k]-pre_sum[i+1])
        //0 1 2 3 pre_sum[4]-pre_sum[3]
        //pre_sum 5
        int result = -1;
        for (int i = 0; i <= v_size-K; i++)
        {
            //… - X[i+K-1]
            int curr = nums[i] - (pre_sum[i + K] - pre_sum[i + 1]);
            int diff = abs(middle - curr);

            if (diff < middle_diff)
            {
                result = i;
                middle_diff = diff;
            }
            else if (diff==middle_diff)
            {
                //如果有多个 i 满足条件，请返回最大的 i
                result = i;
            }
        }
        return result;
    }
    Solution01(vector<int>& nums, int K)
    {
        cout << solve(nums, K);

	    //Solution01
    }
};


/*
给一块n * m的地块，相当于 n * m的二维数组，
每个元素的值表示这个小地块的发电量；
求在这块地上建立正方形的边长为 c的发电站，发电量满足目标电量 k 的地块数量

输入描述
第一行为四个按空格分隔的正整数，分别表示  n，m，c，k。后面 n 行整数，表示每个地块的发电量
输出描述
输出满足条件的地块数量

输入
2 5 2 6
1 3 4 5 8
2 3 6 7 1
输出
4

输入
2 5 2 6（n * m的二维数组2*5，正方形的边长为2的发电站，发电量满足目标电量 6）
1 3 4 5 8
2 3 6 7 1
输出
4

1 3 4
2 3 6 2*2 row_size3-width2
 */

class Solution02
{
public:
    Solution02(vector<vector<int>>&grid, int width, int target)
    {
        row_size = grid.size();
        col_size = grid[0].size();
        //3*5 0 1 2
        vector<vector<int>>pre_sum(row_size + 1, vector<int>(col_size + 1));

        //更新pre_sum
        //pre_sum[r+1][c+1]=pre_sum[r][c+1]+pre_sum[r+1][c]-pre_sum[r][c]+grid[r+1][c+1]
        //row_size 2 col_size-1 4
        for (int r=1; r<=row_size; r++)
        {
	        for (int c=1; c<=col_size; c++)
	        {
                pre_sum[r][c] = pre_sum[r-1][c] + pre_sum[r][c-1] - pre_sum[r-1][c-1] + grid[r-1][c-1];
                //col_size
	        }
            //row_size
        }

        //遍历每个子矩阵
    	//r_begin r_end c_begin c_end
    	//r r+w-1 c c+w-1
        //int row_retangle = pre_sum[r_begin][c_end+1]
		//int col_retangle = pre_sum[r_end+1][c_begin]
        //sub_sum=pre_sum[r_end+1][c_end+1]+pre_sum[r_begin][c_begin]-row_retangle-col_retangle
        int result = 0;
        for (int r=0; r<=row_size-width; r++)
        {
	        for (int c=0; c<=col_size-width; c++)
	        {
                int r_begin = r, c_begin = c, r_end = r + width - 1, c_end = c + width - 1;

                int row_ret = pre_sum[r_begin][c_end + 1];
                int col_ret = pre_sum[r_end + 1][c_begin];

                int bigger_ret = pre_sum[r_end + 1][c_end + 1];
                int repeat_ret = pre_sum[r_begin][c_begin];
                int sub_sum = bigger_ret + repeat_ret - row_ret - col_ret;

                if (sub_sum>=target)
                {
                    result += 1;
                }

	        }
        }
        cout << result;
        //Solution02
    }
private:
    int row_size = 0, col_size = 0;
};

int main()
{
	{
/*
2 5 2 6
1 3 4 5 8
2 3 6 7 1
*/
        int row_size, col_size, width, target;
        cin >> row_size >> col_size >> width >> target;

        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                cin >> grid[r][c];
	        }
        }

        Solution02 solu(grid, width, target);

        return 0;
	}
    //[50,50,2,3],2
    //vector<int>nums = { 50,50,2,3 };
    //int K = 2;
    // 输入数组
    vector<int> nums;
    int temp;
    while (cin.peek() != '\n') {
        cin >> temp;
        nums.push_back(temp);
    }

    // 输入窗口大小K
    int K;
    cin >> K;

    Solution01 solu(nums, K);
    // 输出结果
    //cout << Solution01.solve(nums, K) << endl;

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
